Понятная информатика,
или Давайте учиться дружно!
МБОУ г. Ивантеевка го Пушкинский Московской области
"Образовательный центр № 1"
Практикум для подготовки к ЕГЭ – 2021, задание 5, часть 2. Элементы теории алгоритмов: бит четности и др.
(базовый уровень, примерное время решения – 4 минуты).
При решении заданий 5 ЕГЭ-2021, часть 2 рассматриваются несколько типов задач на алгоритмизацию. При этом нужно учесть,, что алгоритм - это четкий порядок действий, подлежащих выполнению, то есть при решении задач на алгоритмизацию следует внимательно читать условие задачи и точно, аккуратно и без спешки (в этом залог быстрого и точного решения задачи!) выполнять описанные в нем действия.
При этом обратим внимание, что одни и те же действия в разных задачах могут описываться разными условиями, например:
- "складываются все цифры двоичной записи числа" или "считается количество единиц в двоичной записи числа": поскольку сумма цифр двоичной записи числа равна количеству единиц в двоичном числе, то при решении задач быстрее и проще посчитать количество единиц в записи и получить результат для данного условия;
- "остаток от деления суммы (количества единиц) на два", "бит чётности", "четное число или нет" - в результате проверки всех этих условий проверяется остаток от деления числа на 2: по умолчанию это ноль для четного числа и единица - для нечетного. Но в условии задач этот результат может меняться, поэтому следует точно выполнять действия, заданные в алгоритме!
Следует также внимательно смотреть, какое из чисел – N или R – следует искать в данной задаче.
Пример 1 (ДЕМО – 2021)
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится двоичная запись числа N.
- К этой записи дописываются справа ещё два разряда по следующему правилу:
- складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
- над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.
Решение:
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:
1. Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 77) - число 78:
78 = 26 + 23 + 22 + 21 = 10011102
2. Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 100112 и цифры 10, которые получены в результате двух следующих шагов выполнения алгоритма:
- 1 – верно, так как количество единиц в числе N равно трем;
- 0 – верно, так как теперь в полученном результате уже 4 единицы.
Так как условия выполнения алгоритма совпадают с полученным результатом, то искомое число N = 100112 и будет искомым. Переводим его в десятичную систему счисления и получаем ответ:
N = 100112 = 20 + 21 + 02 + 03 + 24 = 1 + 2 + 16 = 19.
Примечание: для быстрого и точного перевода числа из двоичной системы в десятичную я записываю степени с конца, чтобы не делать лишних действий и не допускать возможных ошибок.
Ответ: 19
Пример 2 (1426)
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится двоичная запись числа N.
- К этой записи дописываются справа ещё два разряда по следующему правилу:
- в конец числа (справа) дописывается 1, если число единиц в двоичной записи числа чётно, и 0, если число единиц в двоичной записи числа нечётно;
- к этой записи справа дописывается остаток от деления количества единиц на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает 31 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
Решение:
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:
- Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 31) - число 32: 32 = 25 = 1000002
- Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 10002 и цифры 00, которые получены в результате двух следующих шагов выполнения алгоритма:
- 0 – верно, так как количество единиц в числе N нечетно;
- 0 – неверно, так как остаток от деления количества единиц на 2 равен 1.
Так как условия выполнения алгоритма НЕ совпадают с полученным результатом, то берем следующее возможное число искомое число R = 33 и проверяем его.
1. Переведем число 33 в двоичную систему счисления: 33 = 25 + 1 = 1000012
2. Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 10002 и цифры 01, которые получены в результате двух следующих шагов выполнения алгоритма:
- 0 – верно, так как количество единиц в числе N нечетно;
- 1 – верно, так как результат от деления количества единиц на 2 равен 1.
Так как условия выполнения алгоритма совпадают с полученным результатом, то искомое число N = 110002 и будет искомым. Переводим его в десятичную систему счисления и получаем ответ:
N = 1100112 = 20 + 21 + 02 + 03 + 24 = 1 + 2 + 16 = 19.
Ответ: 33
Пример 3 (1431)
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится двоичная запись числа N.
- К этой записи дописывается справа бит чётности: 0, если в двоичном коде числа N было чётное число единиц, и 1, если нечётное.
- К полученному результату дописывается ещё один бит чётности.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число, большее, чем 96. В ответе это число запишите в десятичной системе.
Решение 1 – короткое:
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:
Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 96) - число 97:
97 = 26 + 25 + 20 = 11000012
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и получаем, что для числа N = 110002 последними цифрами должны быть 00, но тогда число R = 11000002 = 96 не удовлетворяет условию задачи.
Числа с двумя последними цифрами 01 (97 = 11000012), 10 (98 = 11000102) и 11 (99=11000112) также не подходят. Это значит, что нужно увеличивать само число N, тогда получаем N = 110012 и в результате работы алгоритма получим R = 11001102 = 102.
Тогда искомое число N = 110012 = 25
Ответ: 25
Решение 2 – длинное (обычное):
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:
Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 96) - число 97:
97 = 26 + 25 + 20 = 11000012
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110002 и цифры 01, которые получены в результате двух следующих шагов выполнения алгоритма:
- 0 – верно, так как количество единиц в числе N четно;
- 1 –неверно, так как количество единиц в числе N четно.
Так как условия выполнения алгоритма НЕ совпадают с полученным результатом, то берем следующее возможное число R = 98 и проверяем его.
Переведем в двоичную систему число 98:
98 = 26 + 25 + 21 = 11000102
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110002 и цифры 10, которые получены в результате двух следующих шагов выполнения алгоритма:
- 1 – неверно, так как количество единиц в числе N четно;
- 0 – неверно, так как количество единиц в числе N нечетно.
Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 99 и проверяем его.
Переведем в двоичную систему число 99:
99= 26 + 25 + 21 + 20 = 11000112
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110002 и цифры 11, которые получены в результате двух следующих шагов выполнения алгоритма:
- 1 – неверно, так как количество единиц в числе N четно
- 1 – верно, так как количество единиц в числе N нечетно.
Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 100 и проверяем его.
Переведем в двоичную систему число100:
100= 26 + 25 + 22 = 11001002
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110012 и цифры 00, которые получены в результате двух следующих шагов выполнения алгоритма:
- 0 – неверно, так как количество единиц в числе N нечетно
- 0 – неверно, так как количество единиц в числе N нечетно.
Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 101 и проверяем его.
Переведем в двоичную систему число 101:
101= 26 + 25 + 22 + 20 = 11001012
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110012 и цифры 01, которые получены в результате двух следующих шагов выполнения алгоритма:
- 0 – неверно, так как количество единиц в числе N нечетно
- 1 – верно, так как количество единиц в числе N нечетно.
Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 102 и проверяем его.
Переведем в двоичную систему число 102:
102= 26 + 25 + 22 + 21 = 11001102
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110012 и цифры 10, которые получены в результате двух следующих шагов выполнения алгоритма:
- 1 – верно, так как количество единиц в числе N нечетно
- 0 – верно, так как количество единиц в числе N четно.
Так как оба условия выполнения алгоритма совпадают с полученным результатом, то искомое число N = 100112 и будет искомым. Переводим его в десятичную систему счисления и получаем ответ:
N = 110012 = 20 + 01 + 02 + 23 + 24 = 1 + 8 + 16 = 25.
Ответ: 25
Пример 4 (4796)
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) Складываются все цифры двоичной записи числа. Если сумма четная, то в конец числа (справа) дописывается 1, а если нечетная, то дописывается 0. Например, запись числа 10 преобразуется в запись 100;
3) К полученному результату применяется еще раз пункт 2 этого алгоритма.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите количество чисел R, которые могут быть получены в результате работы этого алгоритма, и лежат в диапазоне 16 ≤ R ≤ 32.
Решение:
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону.
Переведем в двоичную систему первое число, удовлетворяющее условию задачи границы диапазона возможных чисел R:
Rmin = 24 = 100002
Rmax = 25 = 1000002
Соответственно получаем Nmin = 22 = 1002 и Nmax = 23 = 10002.
Далее берем все возможные числа N внутри данного диапазона (возможны только три варианта – 101, 110 и 111) и проверяем результат работы алгоритма над ними:
при N = 1012 возможно только одно R = 101102 = 22
при N = 1102 возможно только одно R = 110102 = 26
при N = 1112 возможно только одно R = 111002 = 28
Тогда всего получаем 5 подходящих чисел.
Ответ: 5
Пример 5 (4846).
Автомат обрабатывает натуральное число N < 256 по следующему алгоритму:
1) Строится восьмибитная двоичная запись числа N–1.
2) Инвертируются разряды исходного числа (0 заменяется на 1, 1 на 0).
3) Полученное число переводится в десятичную систему счисления.
Для какого числа N результат работы алгоритма равен 113?
Решение:
Переводим число 113 в двоичную систему счисления и получаем
N - 1 = 26 + 25 + 24 + 20 = 11100012
Дополняем его до восьми бит и инвертируем:
N - 1 = 011100012 => 100011102 = 21 + 22 + 23+ 27 = 142, тогда N = 142 + 1= 143.
Ответ: 143
© 2018–2024 Звездина Вера Алексеевна, v_zvezdina@mail.ru
